package com.zh.note.leetcode.sort;

/**
 * @Author: zhanghuan
 * @date: 2023/5/15 18:04
 * @description: create it
 */
public class SearchUtil {

    /**
     * 前提条件：有序
     * 二分查找
     */
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1; // 定义target在左闭右闭的区间里，[left, right]

        while (low <= high) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int mid = low + (high - low) >> 1; // 防止溢出 等同于(left + right)/2
            if (arr[mid] > target) {
                high = mid - 1; // target 在左区间，所以[left, middle - 1]
            } else if (arr[mid] < target) {
                low = mid + 1; // target 在右区间，所以[middle + 1, right]
            } else {  // nums[middle] == target
                return mid; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }

    public static int binarySearch2(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (low <= high) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = low + ((high - low) / 2);// 防止溢出 等同于(left + right)/2
            if (arr[middle] > target) {
                high = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (arr[middle] < target) {
                low = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {2, 5, 7, 9, 12, 24, 32, 65};
        System.out.println(binarySearch(nums, 22));
    }

}
